Longest turbulent subarray [Sliding Window]

Time: O(N); Space: O(1); medium

A subarray A[i], A[i+1], …, A[j] of A is said to be turbulent if and only if: * For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even; * OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: A = [9, 4, 2, 10, 7, 8, 8, 1, 9]

Output: 5

Explanation:

(A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

Input: A = [4, 8, 12, 16]

Output: 2

Example 3:

Input: A = [100]

Output: 1

Notes:

  • 1 <= len(A) <= 40000

  • 0 <= A[i] <= 10^9

1. Sliding Window

Intuition Evidently, we only care about the comparisons between adjacent elements. If the comparisons are represented by -1, 0, 1 (for <, =, >), then we want the longest sequence of alternating 1, -1, 1, -1, … (starting with either 1 or -1).

These alternating comparisons form contiguous blocks. We know when the next block ends: when it is the last two elements being compared, or when the sequence isn’t alternating.

For example, take an array like [9, 4, 2, 10, 7, 8, 8, 1, 9]. The comparisons are [1, 1, -1, 1, -1, 0, -1, 1]. The blocks are [1], [1,-1,1,-1], [0], [-1,1].

Algorithm Scan the array from left to right. If we are at the end of a block (last elements OR it stopped alternating), then we should record the length of that block as our candidate answer, and set the start of the new block as the next element.

[12]:

class Solution1(object):
    """
    Time: O(N), where N is the length of A.
    Space: O(1).
    """
    def cmp(self, x, y):
        return (x > y) - (x < y)

    def maxTurbulenceSize(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        N = len(A)
        result = 1
        anchor = 0

        for i in range(1, N):
            c = self.cmp(A[i-1], A[i])
            if c == 0:
                anchor = i
            elif i == N-1 or c * self.cmp(A[i], A[i+1]) != -1:
                result = max(result, i - anchor + 1)
                anchor = i
        return result

[13]:

s = Solution1()
A = [9, 4, 2, 10, 7, 8, 8, 1, 9]
assert s.maxTurbulenceSize(A) == 5
A = [4, 8, 12, 16]
assert s.maxTurbulenceSize(A) == 2
A = [100]
assert s.maxTurbulenceSize(A) == 1

[14]:

class Solution2(object):
    """
    Time: O(N), where N is the length of A.
    Space: O(1).
    """
    def cmp(self, x, y):
        return (x > y) - (x < y)

    def maxTurbulenceSize(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        result = 1
        start = 0
        for i in range(1, len(A)):
            if i == len(A)-1 or \
                self.cmp(A[i-1], A[i]) * self.cmp(A[i], A[i+1]) != -1:
                result = max(result, i - start + 1)
                start = i
        return result

[15]:

s = Solution2()
A = [9, 4, 2, 10, 7, 8, 8, 1, 9]
assert s.maxTurbulenceSize(A) == 5
A = [4, 8, 12, 16]
assert s.maxTurbulenceSize(A) == 2
A = [100]
assert s.maxTurbulenceSize(A) == 1